#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;

class Node{
public:
    int val;
    vector<Node *> children;

    //构造函数
    Node(){}

    Node(int _val){
        val = _val;
    }

    Node(int _val,vector<Node*>_children){
        val = _val;
        children = _children;
    }
};

class TreeNode{
public:
    int val;
    TreeNode* left;
    TreeNode *right;
};

//N叉树的层序遍历
vector<vector<int>> levelOrder(Node* root){
    vector<vector<int>> ret;
    if(root==nullptr){
        return ret;
    }
    //创建一个队列
    queue<Node *> q;
    //先将根节点入队
    q.push(root);

    while(!q.empty()){
        //先统计队列当前有多少个节点
        int count = q.size();
        //创建一个数组，存放节点数据
        vector<int> tmp;
        while(count--){
            Node *front = q.front();
            q.pop();

            //将当前节点数据存放到本行数组中
            tmp.push_back(front->val);

            //循环将当前节点的子节点入队
            for(auto child : front->children){
                if(child){
                    q.push(child);
                }
            }
        }
        //将本行数组存放到结果数组中
        ret.push_back(tmp);
    }

    return ret;
}

//103.二叉树的锯齿形层序遍历
vector<vector<int>> zigzagLevelOrder(TreeNode* root){
    vector<vector<int>> ret;
    if(root==nullptr){
        return ret;
    }
    //创建一个队列
    queue<TreeNode *> q;
    //先将根节点入队
    q.push(root);

    //用一个变量标记是偶数行还是奇数行
    int flag = 1;
    while(!q.empty()){
        //先统计队列当前有多少个节点
        int count = q.size();
        //创建一个数组，存放节点数据
        vector<int> tmp;
        while(count--){
            TreeNode *front = q.front();
            q.pop();

            //将当前节点数据存放到本行数组中
            tmp.push_back(front->val);

            if(front->left){
                q.push(front->left);
            }
            if(front->right){
                q.push(front->right);
            }
        }
        //将本行数组存放到结果数组中
        if(flag%2==0){
            reverse(tmp.begin(), tmp.end());
        }
        ret.push_back(tmp);
        flag++;
    }

    return ret;
}

//662.二叉树最大宽度
//因为每一层的个数是2的次方扩展，使用无符号长整形避免下标溢出
//即使标记每一层最左侧和最右侧的下标溢出，两个相减之和就不会溢出
unsigned long long maxwidth=0;
unsigned long long front = 0;
unsigned long long back = 0;
int widthOfBinaryTree(TreeNode* root){
    //创建一个队列，存放的是节点以及节点对应的下标
    queue<pair<TreeNode *, unsigned long long>> q;
    //先将根节点以及下标0入队
    q.push({root, 0});

    while(!q.empty()){
        //获取当前层数的个数
        unsigned long long sz = q.size();
        unsigned long long cur = sz;
        unsigned long long flag = 1; 
        while(cur--){
            pair<TreeNode *, unsigned long long> tmp = q.front();
            q.pop();
            //如果该节点是当前层最左边的，标记当前下标
            if(flag==1){
                front = tmp.second;
            }
            //如果该节点是当前层最右边的，标记当前下标
            if(flag==sz){
                back = tmp.second;
            }

            //如果该节点的左子节点不为空，左子节点节点+对应下标入队
            if(tmp.first->left){
                q.push({tmp.first->left, tmp.second * 2 + 1});
            }
            //如果该节点的右子节点不为空，右子节点节点+对应下标入队
            if(tmp.first->right){
                q.push({tmp.first->right, tmp.second * 2 + 2});
            }
            flag++;
        }
        //当前层结束后，计算当前层的宽度
        maxwidth = max(maxwidth, back - front + 1);
    }

    return maxwidth;
}

//515.二叉树中每一行的最大值
vector<int> largestValues(TreeNode* root){
    vector<int> ret;
    if(root==nullptr){
        return ret;
    }
    //创建一个队列
    queue<TreeNode *> q;
    //根节点入队
    q.push(root);

    while(!q.empty()){
        //先计算当前层的个数
        int sz = q.size();
        //设置一个变量用来找到当前层的最大值
        int maxnum =INT_MIN
        while(sz--){
            TreeNode* front=q.front();
            q.pop();

            //更新最大值
            maxnum = max(maxnum, front->val);

            if(front->left){
                q.push(front->left);
            }
            if(front->right){
                q.push(front->right);
            }
        }

        //将当前层的最大值存放到数组中
        ret.push_back(maxnum);
    }

    return ret;
}

int main(){

    return 0;
}